package bintree.leetcode;

/**
 * @author yuisama
 * @date 2022/09/09 15:49
 * 二叉树最大路径和问题
 **/
public class Num124_MaxPathSum {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        onePathMaxVal(root);
        return max;
    }
    /**
     * 在以root为根的二叉树中，返回单边最大路径（必须过当前根节点）
     * 此问题和寻找lca问题有异曲同工之妙
     * 如果单纯从一个方法去求解，要考虑的边界太多
     * 因此拆分问题，只求单边最大长度
     * 在求解单边长度的过程中顺带不断求解最大路径和问题
     * @param root
     * @return
     */
    public int onePathMaxVal(TreeNode root) {
        // 边界
        if (root == null) {
            return 0;
        }
        // 左子树一侧最大路径和，若都是负数使用0来替代
        int leftVal = Math.max(0,onePathMaxVal(root.left));
        // 右子树同理
        int rightVal = Math.max(0,onePathMaxVal(root.right));
        // 求解当前以root为根的二叉树的最大路径和
        // root.val + left + right一定是以当前root为根的最大路径，左右子树若负数已经拿0代替了
        // 若root.val为负数，最大值存储在后续遍历的max变量中
        max = Math.max(max,leftVal + rightVal + root.val);
        return root.val + Math.max(leftVal,rightVal);
    }
}